package com.chapter4.graph.direct;

import java.util.Stack;

/**'
 * 
* @ClassName: DirectedCycle 
* @Description: 判断有向图是否有环 
* @author minjun
* @date 2015年3月4日 下午10:00:22 
*
 */
public class DirectedCycle {

	private boolean[] marked;
	
	private Stack<Integer> cycle;
	
	private boolean[] onStack;
	
	private int[] edgeTo;
	
	public DirectedCycle(Digraph d){
		int len=d.V();
		marked=new boolean[len];
		onStack=new boolean[len];
		edgeTo=new int[len];
		for(int i=0;i<len;i++){
			if(!marked[i]){
				dfs(d,i);
			}
		}
	}

	private void dfs(Digraph d, int v) {
		onStack[v]=true;
		marked[v]=true;
		for(int w:d.adj(v)){
			if(hasCycle()) return;
			if(!marked[w]){
				edgeTo[w]=v;
				dfs(d, w);
			}else if(onStack[w]){
				cycle=new Stack<Integer>();
				for(int i=v;i!=w;i=edgeTo[i]){
					cycle.push(i);
				}
				cycle.push(w);
				cycle.push(v);
			}
		}
		onStack[v]=false;
	}
	
	public boolean hasCycle(){
		return cycle!=null;
	}
	
	public Iterable<Integer> cycle(){
		return cycle;
	}
}
